import java.util.*;

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        HashMap<String,Integer> map = new HashMap<>();
        //1.遍历words
        for(int i = 0 ;i<words.length;i++){

                if(map.containsKey(words[i])){
                    int val = map.get(words[i]);
                    map.put(words[i],val+1);
            }else {
                    map.put(words[i],1);
                }
        }
        //2.建立K个长度的小根堆
        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(k,
                new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                //频率相同，把字典序大的放在前面
                if(o1.getValue().compareTo(o2.getValue()) == 0){
                    return o2.getValue().compareTo(o1.getValue());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });
        //3.遍历map
        for ( Map.Entry<String,Integer> entry: map.entrySet() ) {
            if(minHeap.size() < k){
                minHeap.offer(entry);
            }else {
                Map.Entry<String,Integer> top = minHeap.peek();
                //如果当前要入堆的元素比堆顶元素大，就弹出堆
                if(entry.getValue().compareTo(top.getValue()) > 0){
                        minHeap.poll();
                        minHeap.offer(entry);
                }else {
                    //频率相同
                    if(entry.getValue().compareTo(top.getValue()) == 0){
                        //key小的入堆
                        if(top.getKey().compareTo(entry.getKey()) > 0){
                            minHeap.poll();
                            minHeap.offer(entry);
                        }
                    }
                }
            }
        }
        //4.转换为List
        List<String> list = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            String str = minHeap.poll().getKey();
            list.add(str);
        }
        //5.反转
        Collections.reverse(list);
        return list;

    }
}